对拉格朗日乘数法和KKT条件的简单理解（来自PRML的附录）

说实在这东西困扰我很久了，但是看了PRML最后的附录之后感觉茅塞顿开，这里讲下我看了之后的理解。

首先我们来提一下拉格朗日乘数法：

假设有一个函数f(x1, x2), 其中函数的限制是g(x1, x2) = 0, 如果我们要解f(x1, x2)，那我们需要做一些什么呢？

方法1

我们可以把限制给解出来，直接表达为x2 = h(x1), 这样一来的话，f(x1, x2)就简单的变成了f(x1, h(x1))，而这种类型的函数，我们的做法也相当简单了，只需要把 f(x1, h(x1)) 关于 x1 的驻点 x1* 给求出来就好了。

但是为什么方法1的可行性不是那么高呢，那是因为大部分时候x1,x2他并不是绝对关联的，一个x2和x1之前可能是互相之间有好几个值对应在一起，一个x1对应10个x2，一个x2同时对应10个x1这种事情都是有可能的，这时候怎么办呢，我们就需要寻求第二种方法。

方法2

我们假设X是一个高维向量。g(x)作为限制方程，结果一直都是0，那样子的话，如果我们对于点x处进行泰勒展开，那么必然有结果g(x+k) = g(x) + k^(T)*g'(x), 其中k是一个无限接近0的向量，我们知道在这个限制曲面上，不论你x怎么取，那么都会在这个限制面上，由于k是平行于这个限制面的，那么一个一直与其相乘为0的值必然正交与这个限制面了。

这时候我们来分析f'(x), 我们知道在g(x)限制条件下，f'(x)也必然与这个限制面正交。不然的话，x只要稍微偏移一点就能使得自身变得更大，f(x)就还会变，这显然和此时f(x)没法再变得更大自相矛盾了。

这时候，结论就来了，既然f'(x)和g'(x)都和限制面正交，他们的x又是同一个x，那么是不是代表这他们肯定是平行的？

所以，我们必然可以给个参数 r 使得f'(x) + r*g'(x) = 0

最后，他们样子就长这个样（图来源于PRML附录）

接下来，我们来讲讲KKT条件

肯定有人问了，我现在能够在g(x)作为一个限制面的条件下成功了，但是如果限制条件不是g(x)不等于0，而是g(x) >= 0，这样我要怎么搞呢？

首先我们对其进行分类讨论，在g(x) > 0的前提下

如果驻点在g(x) > 0的区域内，我们管这个叫做限制条件未激活。

如果驻点在g(x) = 0的边界上，我们管这个叫限制条件激活。

第一种情况下，限制条件就和没有一样，我们不考虑，所以直接就把 r 变成 0，第二种情况就和之前描述的一样，不再赘述。

最后结果就是下面三条公式作为限制条件

g(x) >=0  r >= 0  r*g(x) = 0

推广到有限制条件的泛函的情况也是类似的，可以用SVM的推导练练手，最好加入核函数。